題目說明

題目給定兩個排序後的 array nums1 與 nums2，需回傳兩個 array merge 後的中位數為何

並且題目需要我們在時間複雜度為O(log(m+n))左右

解題思路

這一題如果用 naive 的解法其實不會到 hard，難是難在要在時間複雜度小於 O(n+m) 的狀態下找到答案。
看到兩個以排序陣列找值，就會想到 binary search ，這題重點會擺在，在兩個 array 裡面使用 binary search 找到 merge 後的 list 中位數

程式碼

# Time: log(min(n, m))


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2

        if len(B) < len(A):
            A, B = B, A

        l, r = 0, len(A) - 1
        while True:
            i = (l + r) // 2  # A
            j = half - i - 2  # B

            Aleft = A[i] if i >= 0 else float("-infinity")
            Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
            Bleft = B[j] if j >= 0 else float("-infinity")
            Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")

            # partition is correct
            if Aleft <= Bright and Bleft <= Aright:
                # odd
                if total % 2:
                    return min(Aright, Bright)
                # even
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            elif Aleft > Bright:
                r = i - 1
            else:
                l = i + 1